package b_sort.a_1_bubble_sort;

import static b_sort.StringUtils.printArr;
import static b_sort.StringUtils.printCount;

/**
 * 冒泡排序
 * 时间复杂度    O(n^2)
 * 空间复杂度    O(1)
 * <p>
 * ------
 * 外层 FOR 表明冒泡次数，每次都能确定尾部一个最大值， n 个数只需要 n-1 次比较
 * 内层 FOR 表明相邻两数进行比较，n 个数第一轮只需要 n-1 此比较，第 k 轮只需要 n-1-k 次比较
 *
 * @author FRSF
 * @since 2025/2/26 20:21
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5, 4, 6, 7, 8, 9, 10};
        bubbleSort(arr);
        bubbleSortBetter(arr);
    }

    /**
     * 冒泡排序
     *
     * @param arr 待排序数组
     */
    public static void bubbleSort(int[] arr) {
        printArr(arr);
        int count = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                count++;
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        printArr(arr);
        printCount(count);
    }

    /**
     * 冒泡排序 - 优化版
     * ------
     * 理解一：如果本轮循环已经确定没有进行冒泡交换，那表明当前 相邻有序，从而整体有序
     * 理解二：第 k 轮已经有序，剩下 n-k 个元素再此进行冒泡，冒泡对象是第k轮中元素的子集，k轮有序，所有子集也必有序
     *
     * @param arr 待排序数组
     */
    public static void bubbleSortBetter(int[] arr) {
        printArr(arr);
        int count = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                count++;
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        printArr(arr);
        printCount(count);
    }
}
